class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        // 下面这种做法和昨天那道无重复的最长字串很像，这里不再过多赘述
        if(s.size() < p.size()) return {};
        vector<int> ans;
        int left = 0;
        map<char, int> p_;
        map<char, int> s_;
        for(auto &e : p) p_[e]++;
        cout << "p_[e]: " << p_['e'] << endl; 
        for(int i = 0; i < s.size(); i++)
        {
            s_[s[i]]++;
            while(s_[s[i]] > p_[s[i]])
                s_[s[left++]]--;
            if(s_ == p_)
                ans.push_back(left);
        }
        return ans;


        // 还有下面这种做法，有点像计数排序 + 滑动窗口的思想，可能比上面那种做法好理解一些
        // 因为题目说了：s 和 p 仅包含小写字母
        // 所以我们可以用两个26大小的数组来记录p的字符出现次数，以及当前s中窗口内字符次数(s中窗口大小取决于p)

        vector<int> ans;
        vector<int> count_p(26, 0);
        vector<int> count_s(26, 0);

        int np = p.size();
        for(int i = 0; i < np; i++)
        {
            count_p[p[i] - 'a']++;
            count_s[s[i] - 'a']++;
        }

        // 下面左右边界正是取决于p的大小，只不过在s中体现
        int left = 0;
        int right = np - 1;

        while(right < s.size())
        {
            if(count_p == count_s)
                ans.push_back(left);

            // 接下来窗口往右移动
            count_s[s[left] - 'a']--;
            left++;         // 左边界往右移动，移动之前把s中窗口对应的计数减掉

            // 接下来移动右边界，移动之前判断右边界是否超过了s的大小
            if(++right < s.size())
                count_s[s[right] - 'a']++;
        }
        return ans;
    }
};